

package classes;



public class Core {

  private int n, m;
  private VertexList P;     // il poligono in ingresso
  public  VertexList ris;    // il poligono in sucita
  private Pointi A, B;         /* directed edges on P and Q (resp.) */
  private int     cross;       /* sign of z-component of A x B */
  private int     bHA, aHB;    /* b in H(A); a in H(b). */
  private Pointi Origin;       /* (0,0) */
  private boolean FirstPoint;  /* Is this the first point? (used to initialize).*/
  private Pointd p0;           /* The first point. */
  private int     code;        /* SegSegInt return code. */ 
  boolean convex=true;
  
  Core() 
  {
    
  }
  

  public boolean Start(VertexList p) 
  {
    convex=true;   
    
    //creiamo la vertexist di p
    this.P = new VertexList();
    
    //copiamo p in input in P 
    p.ListCopy(P);
 
        
    //facciamo un test sulla convessità di P (eventualmente usciamo)
    if (!CheckForConvexity()) {
        convex=false;
        System.out.println("Polygons are not convex...");
        return false;
    }
            
            
    //altrimenti andiamo avanti        
    else {
      System.out.println("Polygons are convex...");
      n = P.n;    //in n mettiamo il numero di vertici di vertici di P
      
      //creiamo l'istanza di ris per il punto risultato
      ris = new VertexList();
      
      //lanciamo il metodo FindExtreme che prende P e n 
      //tale metodo riempe ris con il  punto estremo
      FindExtreme( P, n);
    }
    return true;
  }
  
  
  
  
  private double  Dot( Pointi a, Vertex b ) //prodotto scalare
  {
    double sum = 0.0;
    sum = a.x * b.v.x + a.y * b.v.y;
    return  sum;
  }
  
    
  private boolean  up( Pointi a, Vertex b ) //test per prodotto scalare positivo
  {
   boolean up=false;
   double sum=Dot (a,b);
   if (sum>0) up=true;
   return up;
  }
  
      
  private boolean  down( Pointi a, Vertex b ) //test per prodotto scalare negativo
  {
   boolean down=false;
   double sum=Dot (a,b);
   if (sum<0) down=true;
   return down;
  }
  
    
 
  private double Dr (Pointi u, Vertex a, Vertex b)  //prodotto scalare tra u e la differenza tra a e b
  {    Vertex c= new Vertex();
       c.v.x=a.v.x-b.v.x;
       c.v.y=a.v.y-b.v.y;
       double sign=0.0;
       sign=Dot(u,c);
       return sign;
  }
    
 
   
  private boolean above (Pointi u, Vertex a, Vertex b) //test per vedere se il vertice a è sopra il vertice b
  {    
       double sign= Dr(u,a,b);
       if (sign>0)return true; 
       else return false;
  }
  
   
  private boolean below (Pointi u, Vertex a, Vertex b) //test per vedere se il vertice a è sotto il vertice b
  {    
       double sign= Dr(u,a,b);
       if (sign<0)return true; 
       else return false;
  }  
  
  

  //pulisce i VertexList
  public void ClearConvConv()
  {
    P.ClearVertexList();
    ris.ClearVertexList();
  }

  
  //metodo che verifica la convessità del poligono
  private boolean CheckForConvexity()
  { 
    //se la lista di vertici P non risulta in verso antiorario, la inverto 
    //se non sono in senso antiorario il test LeftOn non funziona  
    if (P.Ccw() != 1)	
      P.ReverseList();
    
    //richiama il metodo della classe VertexList: CheckForConvexity() che effettua la verifica 
    if (!P.CheckForConvexity())
      return false;
 
    return true;
  }

  
  
  
   private void FindExtreme( VertexList P, int n ) // qui va l'algortimo vero e proprio di ricerca estremi
 
  {
      Vertex[] vvv = new Vertex[n]; //creo un array di vertici con dimensione n
      // u è un pointi ma, avendo 2 coordinate x,y, può essere usato nel prodotto scalare come se fosse un vettore
      // u serve per scegliere la direzione di ricerca dell'estremo: estremo lungo x o estremo lungo y.
      // in questo caso (0,1) cerca l'estremo lungo y; se fosse (1,0) lo cercherebbe lungo x
      Pointi u = new Pointi(0,1);   

     
      // creo tre vertici da usare nell'algoritmo
      Vertex max = new Vertex(0,0);
      Vertex a = new Vertex(); 
      Vertex b= new Vertex();
      
      // a è il primo vertice della vertex list; b segue a
      a = P.head; 
      b=a;
      
      //contatori
      int aa = 0;
      int bb=0;
  
      //copio tutti i vertici nell'array in modo da averli in due diversi formati, da scegliere all'occorrenza.
      while (aa<n) 
        {  
           vvv[aa]=P.GetElement(aa);
           a=a.next;
           aa++;
        }
        
      
      if (n<10)  //se il numero di vertici è piccolo uso la ricerca forza bruta
      {    
          
           max.v.x=a.v.x; //a è il momentaneo max
           max.v.y=a.v.y;
            
        while (bb<n) 
        {  
                               
           if (above(u,a,b)) //controlla se a è più in alto di b rispetto a u
                {
                 max.v.x=a.v.x; //a è il momentaneo max
                 max.v.y=a.v.y;
                 b=max;
                }
           
           a=a.next; //vai avanti
           bb++;
           
        }
           InsertRis (max.v.x, max.v.y); //inserisci in Ris il max trovato alla fine della scansione
      }
      
      else  // se il numero di vertici è elevato uso la ricerca binaria
          
      {
          
      //inizializza tutti gli indici da usare nella ricerca binaria
      int as=0;
      int bs=n; 
      int cs=0;
      int I=0;
      
      boolean upA, upC; //test per la direzione up di A e C
      
      
            
      //creiamo due vertici da usare nei test
      Vertex AS = new Vertex(); 
      Vertex CS = new Vertex();
      Vertex ASA = new Vertex(); 
      
      // l'intervallo di partenza è [0,n] con vvv[n]=vvv[0]
      // il vertice AS è dato da vvv[1]-vvv[0]
      AS.v.x=vvv[1].v.x-vvv[0].v.x;
      AS.v.y=vvv[1].v.y-vvv[0].v.y;
      
      upA = up(u,AS); //valuta se vvv[1] è più in alto di vvv[0] rispetto ad u
     
      ASA.v.x=vvv[0].v.x-vvv[n-1].v.x;
      ASA.v.y=vvv[0].v.y-vvv[n-1].v.y;
      
      upC = up(u,ASA); //valuta se vvv[0] è più in alto di vvv[n-1] rispetto ad u
      
   
     boolean procedi=true;
        
      // verifica se vvv[0] o vvv[n-1] è il massimo locale
     
      if (!upA && !above(u, vvv[n-1], vvv[0]))    
          {
          I=0; // vvv[0] è il massimo
          procedi=false;
          }
      
      if (!upC && !above(u, vvv[n-2], vvv[n-1]))    
          {
          I=n-1; // vvv[n-1] è il massimo
          procedi=false;
          }

     while(procedi) { 
     
        cs = (as + bs) / 2;       // cs è il punti intermedio di [as,bs] e 0<cs<n
        
        //il vertice CS sarà vvv[cs+1]-vvv[cs]
        CS.v.x = vvv[cs+1].v.x - vvv[cs].v.x;
        CS.v.y = vvv[cs+1].v.y - vvv[cs].v.y;

        upC = up(u,CS); //controllo se  vvv[cs+1] è più in alto di vvv[cs]
        
        if (!upC && !above(u,vvv[cs-1],vvv[cs]))
            I=cs;                       // vvv[cs] è il massimo locale (finito)

        // altrimenti continuiamo con la ricerca binaria
        // selezionamo un sottointervallo di [as,bs]: o [as,cs] o [cs,bs]
        if (upA) {                      // se A punta verso l'alto
            
            if (!upC) {                     // se C punta verso il basso
                bs = cs;                      // scelgo l'intervallo [as,cs]
            }
            else {                          // se C punta in alto
                if (above(u,vvv[as],vvv[cs])) {       // devo verdificare chi sia pià altro tra as e cs (se as più alto)
                    bs = cs;                      // scelgo l'intervallo [as,cs]
                }
                else {                          // se, invece as è sotto cs
                    as = cs;                      // uso l'intervallo [cs,bs]
                    
                    AS.v.x = CS.v.x;
                    AS.v.y = CS.v.y;
                    
                    upA = upC;
                }
            }
        }
        
        else {             // se A punta verso il basso 
            
            if (upC) {                      // se C punta verso l'alto
               as = cs;                      // uso l'intervallo  [cs,bs]
               
               AS.v.x = CS.v.x;
               AS.v.y = CS.v.y;
               
               upA = upC;
            }
            
            else {                          // se C punta in basso
                if (below(u,vvv[as],vvv[cs])) {       // se vvv[as] è sotto vvv[cs]
                    bs = cs;                      // uso l'intervallo [as,cs]
                }
                
                else {                          // se vvv[as] è sopra vvv[cs]
                    as = cs;                      // uso l'intervallo  [cs,bs]
                
                    AS.v.x = CS.v.x;
                    AS.v.y = CS.v.y;
                    
                    upA = upC;
                }
            }
        }
            
        if (bs <= as+1) {      //abbiamo terminato la ricerca
            procedi=false;}
          
 
                 
    }
     
    InsertRis (vvv[I].v.x,vvv[I].v.y); // in corrispondenza di I ho il valore max e lo inserisco nella lista Risultato
     
      }
  }

  
  
  private void InsertRis(double x, double y) //inserisci il vertice v (x,y) nella lista
  {
    Vertex v = new Vertex((int)x, (int)y);
    ris.InsertBeforeHead(v);
  }


}
